/**
 * x 的平方根
 *
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 *
 * 示例 1：
 * 输入：x = 4
 * 输出：2
 *
 * 示例 2：
 * 输入：x = 8
 * 输出：2
 * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 *
 * 提示：
 * 0 <= x <= 231 - 1
 */

/**
 * 二分, 我们不断的去把给我们的数除二, 寻找他的中间数, 让这个中间数乘以它本身
 * 我们注意, 因为有的数的平方数不是整数, 我们这一题是向下取整的, 所以我们在使用
 * 二分查找的时候, 我们的区间就要选好了
 * 怎么选区间呢?
 * 首先我们要知道咱是一定不能去动右边的边界的, 因为我们是向下取整的, 所以右区间在
 * 不满足条件的时候是不能改变的, 想明白了这一点, 我们就去改变左边界, 那么我们相应
 * 的求中间数就要去取靠左边的数
 * 这中间是有一个要注意的点, 就是我们要注意 int 的范围, 我们在进行比较的时候要用 long
 * 时间复杂度 : O(log(n))
 * 空间复杂度 : O(1)
 */

public class Main {

    // ***********************************
    // 这里用递归写

    // 全局变量, 记录目标值
    int target;

    public int mySqrt1(int x) {

        // 初始化
        target = x;


        return (int) findMid(0, (long)x);
    }

    private long findMid (long x, long y) {

        // 要是边界相等就返回
        // 出口
        if (x == y) {
            return x;
        }

        // 求中间数的时候要取靠右边的一个
        long mid = x + (y - x) / 2 + 1;

        if (mid * mid < target) {

            // 小于的话边界一定不要动
            return findMid(mid, y);

        } else if (mid * mid > target) {

            // 大于的话, 改变右边界
            return findMid(x, mid - 1);

        } else {

            // 找到目标值返回
            return mid;

        }
    }

    // ****************************************
    // 标准一点的写法
    public int mySqrt(int x) {

        // 不用递归, 用 while 来写
        int left = 1, right = x;

        // 这里特判一下
        if(x < 1) return 0;
        if(x == 1) return 1;

        while(left < right) {

            // 取 靠右边的数
            long mid = left + (right - left + 1) / 2;

            // 小于等于的话不要动左边界
            if(mid * mid <= x) left = (int)mid;

            // 大于的话改变右边界
            else right = (int)mid - 1;
        }

        // 最后出来一定是相等的, 直接返回就可以了
        return left;
    }

    public static void main(String[] args) {
        Main test = new Main();
        test.mySqrt(2147395599);
    }
}